The present invention relates generally to content addressable memory (CAM) devices, and more particularly to accessing multiple match locations in a CAM device.
A content addressable memory (CAM) device is a storage device that can be instructed to compare a specific pattern of comparand data with data stored in its associative CAM array. The entire CAM array, or segments thereof, are searched in parallel for a match with the comparand data. The CAM device typically indicates if a match occurs by asserting a match flag, and also typically indicates if multiple matches occur by asserting a multiple match flag. The CAM device can then be instructed to output the highest priority match address or index, data stored in one or more CAM cells at the matching address, and other status information including the match flags, a full flag, validity bits (e.g., skip and empty bits), and other status information.
It would be desirable to provide a CAM device that can efficiently access the highest priority matching location in response to a first instruction, and then access a subsequent lower priority matching location in response to a single second instruction.
A content address memory (CAM) device is disclosed that implements a read next highest priority or xe2x80x9cRNHPMxe2x80x9d instruction. The CAM device initially searches its CAM locations for a match with comparand data. If multiple matches are identified, then the CAM device initially outputs the highest priority matching address. The CAM device may output the highest priority matching address in the same system or a later clock cycle in which the compare instruction was provided. The CAM device may also output data stored in one or more of the CAM cells located at the highest priority matching location and/or status information including the match flags, a full flag, validity bits (e.g., skip and empty bits), and other status information. An RNHPM instruction may then be provided to the CAM device in the next clock cycle or a later clock cycle and cause the next highest priority matching address to be output by the CAM device. The next highest priority matching address may be output in the same or subsequent cycle as the RNHPM instruction and may also cause the CAM device to output data stored in one or more of the CAM cells located at the next highest priority matching location and/or status information for that location. RNHPM instructions can continue to be supplied to the CAM device until no further matching locations are detected.
For one embodiment, the CAM array includes a column of multiple match (xe2x80x9cMMRxe2x80x9d) bits that are used by the RNHPM instruction to resolve a multiple match condition. The MMR bits store an indication of whether the corresponding CAM location has a match with the comparand data. For one example, the MMR bits are set to logic zeros at the beginning of the initial compare instruction. When it is determined which locations in the CAM array match the comparand data, then the MMR bits for those locations are updated to a logic one except for the highest priority matching location. In response to a subsequent RNHPM instruction, only the MMR bits need to be queried (e.g., compared with a logic one) to determine the next highest priority matching location. The match address of the next highest priority matching location, data stored in one or more of the CAM cells at the next highest priority matching location, and/or other status information may then be output from the CAM device. The MMR bit for that matching location is then reset to a logic zero such that a subsequent RNHPM instruction can then access lower priority matching locations by using the MMR bits.
Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description which follows below.